1. Two Sum (Easy)

Question

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

1. You may assume that each input would have exactly one solution, and you may not use the same element twice
2. You can return the answer in any order

Example 1

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1]

Example 2

Input: nums = [3,3], target = 6
Output: [0,1]

Solution 1: Brute Force

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        N = len(nums)
        ans = []
        for i in range(N):
            for j in range(i + 1, N):
                if nums[i] + nums[j] == target:
                    ans = [i, j]
                    break
            if ans:
                break
                
        return ans

Time Complexity: O(N^2)
Space Complexity: O(1)

Solution 2: Hash

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        ans = []
        dic = {}
        for i, v in enumerate(nums):
            diff = target - v
            
            # diff hit
            if diff in dic:
                ans = [dic[diff], i]
                break
            # diff not hit
            else:
                dic[v] = i
                
        return ans

Time Complexity: O(N)
Space Complexity: O(N)

Reference

N/A

Follow-up: 167. Two Sum II - Input Array Is Sorted

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:        
        ptrHead = 0
        ptrTail = len(nums) - 1
        while(ptrHead < ptrTail):
            res = nums[ptrHead] + nums[ptrTail]
            if res == target:
                return [ptrHead + 1, ptrTail + 1]
            elif res > target:
                ptrTail -= 1
            # res < target
            else:
                ptrHead += 1
        return []

Time Complexity: O(N)
Space Complexity: O(1)

2. Add Two Numbers (Medium)

Question

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list

1. You may assume the two numbers do not contain any leading zero, except the number 0 itself

Example 1

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807

Example 3

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

Solution 1: LinkedList

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummyHead = ListNode()
        ptrCurr = dummyHead
        res = 0
        while(l1 or l2 or res):
            if l1:
                res += l1.val
                l1 = l1.next
            if l2:
                res += l2.val
                l2 = l2.next
            
            nxtDigit = ListNode(res % 10)
            ptrCurr.next = nxtDigit
            ptrCurr = ptrCurr.next
            res = int(res / 10) # Carry
            
        return dummyHead.next

Time Complexity: O(N)
Space Complexity: O(N)

Reference

https://leetcode.com/problems/add-two-numbers/discuss/2568116/Short-oror-C%2B%2B-oror-Java-oror-PYTHON-oror-Explained-Solution-oror-Beginner-Friendly-oror-BY-MR-CODER

Follow-up: 445. Add Two Numbers II

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        l1 = self.reverse(l1)
        l2 = self.reverse(l2)
        
        dummyHead = ListNode()
        ptrCurr = dummyHead
        res = 0
        while(l1 or l2 or res):
            if l1:
                print("l1", l1.val)
                res += l1.val
                l1 = l1.next
            if l2:
                print("l2", l2.val)
                res += l2.val
                l2 = l2.next
            
            nxtDigit = ListNode(res % 10)
            ptrCurr.next = nxtDigit
            ptrCurr = ptrCurr.next
            res = int(res / 10) # Carry
            
        ans = self.reverse(dummyHead.next)
        return ans
    
    def reverse(self, head):
        if head is None or head.next is None:
            return head
        
        revHead = self.reverse(head.next)
        head.next.next = head
        head.next = None
        return revHead

Time Complexity: O(N)
Space Complexity: O(N)

題庫出處

LeetCode Top 100 Liked 点赞最高的 100 道算法题